\documentclass{article}
\usepackage{polski}
\usepackage[utf8]{inputenc}
\usepackage{listings}
\usepackage[usenames,dvipsnames]{color} % For colors and names
\usepackage{amsmath}
\usepackage{graphicx}
\usepackage{tabularx}
\title{Laboratorium Rozpoznawania Obrazów \\ ćwiczenie 5-6: rozpoznawanie cyfr z wykorzystaniem sieci neuronowych } % Title


\textwidth = 400pt
\oddsidemargin = 30pt
\hyphenpenalty = 1000

\author{Tomasz \textsc{Bawej}} % Author name

\definecolor{mygrey}{gray}{.96} % Light Grey
\lstset{language=Verilog, tabsize=3, backgroundcolor=\color{mygrey}, basicstyle=\small \ttfamily, commentstyle=\color{BrickRed}}
\lstset{ 
	language=[ISO]C++,              % choose the language of the code ("language=Verilog" is popular as well)
   tabsize=3,							  % sets the size of the tabs in spaces (1 Tab is replaced with 3 spaces)
	basicstyle=\scriptsize,               % the size of the fonts that are used for the code
	numbers=left,                   % where to put the line-numbers
	numberstyle=\scriptsize,              % the size of the fonts that are used for the line-numbers
	stepnumber=2,                   % the step between two line-numbers. If it's 1 each line will be numbered
	numbersep=5pt,                  % how far the line-numbers are from the code
	backgroundcolor=\color{mygrey}, % choose the background color. You must add \usepackage{color}
	%showspaces=false,              % show spaces adding particular underscores
	%showstringspaces=false,        % underline spaces within strings
	%showtabs=false,                % show tabs within strings adding particular underscores
	frame=single,	                 % adds a frame around the code
	tabsize=3,	                    % sets default tabsize to 2 spaces
	captionpos=b,                   % sets the caption-position to bottom
	breaklines=true,                % sets automatic line breaking
	breakatwhitespace=false,        % sets if automatic breaks should only happen at whitespace
	%escapeinside={\%*}{*)},        % if you want to add a comment within your code
	commentstyle=\color{BrickRed},   % sets the comment style
	columns=fixed
}

\begin{document}

\maketitle % Insert the title, author and date

\setlength\parindent{0pt} % Removes all indentation from paragraphs

\renewcommand{\labelenumi}{\alph{enumi}.} % Make numbering in the enumerate environment by letter rather than number (e.g. section 6)

\section{Opis metody klasyfikacji znaków.}
Klasę każdej z~próbek podanych na~wejście sieci wyznacza neuron warstwy wyjściowej o~najwyższej wartości funkcji aktywacji. W najprostszym wydaniu sieć składa się z~$k_{in}+1$ neuronów wejściowych oraz~$k_{out}$ neuronów wyjściowych, gdzie $k_{in}$ jest liczbą cech klasyfikowanych próbek, a~$k_{out}$ jest liczbą klas. Dodatkowy neuron wejściowy pełni rolę normalizującą i~ma~domyślnie przypisaną wartość funkcji aktywacji równą~$-1$. Neurony normalizujące są~także dodawane do~każdej z~ukrytych warstw sieci, o~ile sieć takowe posiada.
Poszczególne pary następujących po~sobie warstw sieci są~połączone ze~sobą zbiorami krawędzi o~ustalonych wagach. Krawędzie te~łączą każdy neuron warstwy bliższej wejściu sieci z~każdym, oprócz normalizującego, neuronem warstwy bezpośrednio następnej oraz umożliwiają propagację wzbudzeń wgłąb sieci, zgodnie z~klasyczną ideą sieci neuronowej bez sprzężeń zwrotnych. W~ramach tej, wzbudzenia $a$~poszczególnych neuronów wyznaczane są w następujący sposób:
\begin{itemize}
\item dla neuronu $i$ warstwy wejściowej: $a^{(1)}_i = X(i)$, gdzie $X$ jest przykładem, a~$i$~wartością jego $i$-tej cechy
\item dla neuronu $i$~warstwy $l>1$, $k(l)$ oznaczającego liczbę neuronów warstwy $l$~oraz $\theta^{(l)}_{ji}$ będącego wagą krawędzi łączącej wyjście neuronu $j$~warstwy $l$~z~wejściem neuronu $i$~warstwy $l+1$: 
$$a^{(l)}_i=sigmoid(\sum_{j=1}^{k(l-1)}\theta^{(l-1)}_{ji}*a^{(l-1)}_{j})$$ 
oraz oczywiście:
$$sigmoid(t)=\frac{1}{1+e^{-t}}$$
\end{itemize}


\pagebreak

\section{Opis algorytmu uczenia klasyfikatora.}

Uczenie sieci zostało zaimplementowane w funkcji \texttt{train}, przyjmującej następujące parametry:
\begin{itemize}
\item{\texttt{layers}} - wektor wierszowy określający strukturę wewnętrzną sieci (warstwy ukryte), np. \texttt{[]}, \texttt{[100]}, \texttt{[30, 40]} itp.
\item{\texttt{lRate}} - początkowa wartość współczynnika uczenia dla każdej z krawędzi
\item{\texttt{data}} - dane treningowe (jeden wiersz - jeden przykład)
\item{\texttt{labels}} - wektor kolumnowy etykiet danych
\item{\texttt{minTrnErr}} - minimalny średni błąd absolutny neuronów wyjściowych na zbiorze treningowym (składowa kryterium stopu)
\item{\texttt{stagnationThreshold=20}} - limit iteracji zastoju procesu uczenia klasyfikatora (składowa kryterium stopu)
\item{\texttt{validationSet=0.075}} - liczba z zakresu $(0; 1)$ określająca część zbioru treningowego przeznaczoną do walidacji klasyfikatora lub zbiór walidujący w postaci wierszy zakończonych etykietą próbki 
\item{\texttt{maxIter=1000}} - bezwzględny limit iteracji            
\item{\texttt{E=1}} - parametr inicjalizacji wag sieci            
\item{\texttt{up=1.2}} - współczynnik skalowania wag "w górę"
\item{\texttt{down=0.5}} - współczynnik skalowania wag "w dół"
\item{\texttt{weights=\{\}}} - początkowe wartości wag sieci (jeśli podane, wykorzystywane jako punkt wyjściowy treningu)
            
\end{itemize}

Funkcja \texttt{train} zwraca dwie wartości:
\begin{itemize}
\item maxScoreNet - sieć neuronowa w postaci listy macierzy wag; zawiera wagi sieci o~najlepszym wyniku walidacji uzyskanym w ramach procesu uczenia.
\item history - sekwencja średnich błędów absolutnych odnotowanych w kolejnych iteracjach dla neuronów warstwy wyjściowej.
\end{itemize}

Centralną rolę w procesie uczenia sieci odgrywa algorytm wstecznej propagacji błędu z~gradientową minimalizacją wartości funkcji kosztu zdefiniowanej następująco:
$$J(\theta)=-\frac{1}{m}[\sum_{i=1}^{m} \sum_{k=1}^{k_{out}} y_k^{(i)}\log {h_\theta(x^{(i)})_k} 
	+(1-y_k^{(i)})\log{(1-h_\theta(x^{(i)})_k)}]$$
	gdzie $m$ oznacza liczbę przykładów, $k_{out}$ liczbę klas (neuronów wyjściowych), $h_{\theta}(x^{(i)})$ wartość hipotezy (wskazania sieci) dla przykładu $i$, a $y_k^{(i)}$ wynosi $0$ lub $1$. \\

Zanim jednak rozpocznie się trening sieci, dane treningowe oraz testowe są~normalizowane. Funkcja \texttt{featureNormalize} najpierw normalizuje dane treningowe, usuwając z nich parametry o~zerowej wariancji, by~następnie wg~uzyskanych dla zbioru treningowego parametrów powtórzyć procedurę na~zbiorze testowym. Parametry normalizacji zwracane są przez funkcję jako dodatkowe wartości.

Pierwszy krok algorytmu stanowi wyznaczenie odpowiedzi sieci na~zadany zbiór parametrów wejściowych. 
Odpowiedź ma~postać wektora wartości z~przedziału $[0; 1]$ o~długości $k_{out}$.
 	$$[a^{(L)}_1, a^{(L)}_2, a^{(L)}_3, ...,  a^{(L)}_{k_{out}},]$$
Liczby te~odpowiadają wartościom funkcji aktywacji poszczególnych neuronów warstwy wyjściowej. Stanem pożądanym jest uzyskanie wartości $0$ dla wszystkich wyjść za~wyjątkiem tego, które odpowiada klasie analizowanego przykładu. Wówczas pożądana wartość funkcji aktywacji wynosi $1$. Różnice pomiędzy faktycznymi, a~pożądanymi wartościami wyjścia równe są~błędom poszczególnych neuronów wyjściowych. Błąd ten jest następnie wzdłuż odpowiednich krawędzi i~proporcjonalnie do~ich wag propagowany do~neuronów wewnątrz sieci. Wyznaczona w ten sposób dla każdego z~neuronów warstw ukrytych wartość mnożona jest przez pochodną funkcji aktywacji danego neuronu i~określana jako $\delta$). W przypadku neuronów wyjściowych, wartość $\delta$ jest bezpośrednio wyznaczana jako błąd wyjścia.
Na podstawie wartości $\delta$, wartości funkcji aktywacji neuronów poprzedniej warstwy oraz wartości współczynnika uczenia $\eta$ korekta wagi krawędzi łączącej neurony: $i$ warstwy $l-1$ oraz $j$~warstwy $l$ obliczana jest według wzoru:
$$-\eta * a^{(l-1)}_i * \delta^{(l)}_j $$
Korekty, obliczone w~powyższy sposób dla każdej z~krawędzi, uśrednia się~dzieląc przez liczbę przykładów $m$ oraz dodaje do~wartości wag. Wartość współczynnika uczenia danej krawędzi jest ponadto skalowana w~górę lub dół, w~zależności od tego, czy korekta zachowuje czy~zmienia znak pomiędzy dwiema iteracjami. Wartości współczynników skalowania korekty określają parametry \texttt{up} i \texttt{down}.



Powyższe czynności powtarzane są do~osiągnięcia kryterium stopu, wyznaczanego na podstawie średniego błędu absolutnego neuronów warstwy wyjściowej oraz wskaźnika postępu na~zborze walidacyjnym. Przede wszystkim, średni błąd neuronów wyjściowych musi spaść poniżej poziomu zadanego parametrem \texttt{minTrnErr}. Wówczas kryterium stopu sprowadza się do osiągnięcia zadanej parametrem \texttt{stagnationThreshold} liczby iteracji zastoju procesu uczenia. Iteracja algorytmu podwyższa licznik zastoju, jeśli wynik walidacji jest niższy od~najwyższego dotychczas osiągniętego lub taki sam, lecz wskaźnik błędu na zbiorze treningowym jest wyższy niż w~iteracji wyznaczającej początek bieżącego okresu zastoju. Jeśli warunek inkrementacji licznika zastoju nie zostanie spełniony, licznik jest zerowany.
Ponadto osiągnięcie określonego parametrem funkcji bezwzględnego limitu iteracji przerywa proces uczenia.

\section{Jakość klasyfikatorów}

Celem wyboru odpowiedniej kombinacji formatu danych oraz architektury sieci, przeprowadzono dwa doświadczenia polegające na wsadowym tworzeniu określonej liczby sieci o~różnych topologiach i~operujących na różnych danych. Tworzone w ramach doświadczenia sieci były każdorazowo eksportowane do plików celem poddania ich pełniejszej analizie w~późniejszym czasie.
Rozpatrywane formaty danych zawierały: dane w surowej postaci, dane o~liczbie wymiarów zredukowanej do~49 i~40 składowych głównych oraz dane przeskalowane z~rozmiaru 28x28 do 7x7 poprzez sumowanie 	wartości w odpowiednich obszarach macierzy źródłowych. Dla każdego z wymienionych formatów stworzono osobny plik inicjalizujący doświadczenie: \texttt{init\_(...).m}, a samo doświadczenie uruchamiano ładując odpowiednio zmodyfikowaną wersję pliku \texttt{batchTrain.m}.
Klasyfikatory ćwiczono na pełnym zestawie danych treningowych, a w charakterze zbioru walidującego wykorzystano zbiór testowy. Pozwoliło to na żywo oceniać zdolność generalizacji klasyfikatorów bez nadmiernego zubożenia zbioru uczącego.
Wyniki oraz komentarze do eksperymentów przedstawiono poniżej (kolumna "neurony warstw ukrytych" zawiera sekwencję liczb odpowiadającą liczbie neuronów w kolejnych warstwach ukrytych sieci).

\input{eksperyment1.tex}

\input{eksperyment2.tex}
 
\input{eksperyment3.tex}


\section{Macierz pomyłek, wyznaczanie oraz weryfikacja poziomu ufności klasyfikatorów.}
Badanie jakości klasyfikatora umożliwiają dwie funkcje: \texttt{evaluate(siec, dane, etykiety)} oraz \texttt{evaluateWithConfidence(siec, dane, etykiety, poziom\_pewności)}.
Pierwsza z funkcji zwraca odsetek poprawnie sklasyfikowanych znaków oraz macierz pomyłek - obie wartości uzyskane dla klasyfikatora nieuchylającego się od odpowiedzi.
Druga funkcja zwraca natomiast odsetek błędnie sklasyfikowanych próbek, odsetek próbek odrzuconych oraz macierz pomyłek - wszystkie wyznaczone dla zadanego poziomu pewności, wyznaczanego przez podzielenie największej spośród wartości funkcji aktywacji neuronów wyjściowych przez sumę wartości funkcji aktywacji wszystkich neuronów wyjściowych (odpytywanie sieci o klasę zbioru próbek realizuje funkcja \texttt{tellClass}, która jako domyślne minimum poziomu ufności przyjmuje 0, a oprócz głównej wartości, etykiety klasy, zwraca także poziom ufności dla danej decyzji.).
Proces ładowania danych i sieci oraz wyznaczania i weryfikacji poziomu ufności ilustruje poniższy wydruk.

\begin{lstlisting}
> source init_pca49.m
> load "data/pca49.500.ver.1.score.0.978400.nn"
> [ans conf] = tellClass(ed, net);
> mean(conf)
ans =  0.96671
> [score mx] = evaluate(net, ed, el)
score =  0.97840
mx =

    972      0      0      1      0      1      2      1      2      1      0
      0   1124      3      2      0      0      2      0      4      0      0
      4      0   1007      5      0      1      1      9      5      0      0
      0      0      4    990      1      5      0      5      4      1      0
      0      0      2      0    964      0      2      2      0     12      0
      2      0      0     11      1    864      5      2      6      1      0
      4      2      2      0      5      1    940      0      4      0      0
      1      2      7      2      2      0      0   1003      2      9      0
      3      1      3      8      2      4      3      5    941      4      0
      5      2      0      4      7      4      2      3      3    979      0

\end{lstlisting}

Następnie wywołując funkcję \texttt{tellClass} dla całego zbioru testowego wyznaczyć można średnią wartość ufności, dla której klasyfikator podejmuje błędne decyzje. Używając tej wartości jako wartości progowej poziomu ufności otrzymano:

\begin{lstlisting}
[errors rejections mx]=evaluateWithConfidence(net, ed, el, 0.71829)
errors =  0.010600
rejections =  0.034400
mx =

    955      0      0      1      0      0      1      1      1      0     21
      0   1118      3      2      0      0      0      0      3      0      9
      3      0    986      3      0      0      0      7      2      0     31
      0      0      1    953      0      3      0      3      3      0     47
      0      0      0      0    947      0      0      0      0      4     31
      2      0      0      6      0    836      1      2      1      0     44
      3      2      0      0      3      1    915      0      1      0     33
      1      1      5      1      1      0      0    981      1      2     35
      1      0      1      6      0      2      3      1    909      2     49
      2      1      0      3      4      1      1      1      2    950     44

\end{lstlisting}

Następnie, w~zależności od natury problemu, zachowanie klasyfikatora można regulować zmieniając wartość minimalnego poziomu ufności. Na~potrzeby doświadczenia przyjęto za cel znaleźć taką wartość, dla której spadek błędu nie będzie pociągał za sobą odrzucenia zbyt wielu poprawnie klasyfikowanych próbek. Uzyskane wyniki przedstawia wydruk na następnej stronie.

\pagebreak 

\begin{lstlisting}
> [errors rejections mx]=evaluateWithConfidence(net, ed, el, 0.57)
errors =  0.016000
rejections =  0.012900
mx =

    966      0      0      1      0      0      1      1      1      0     10
      0   1121      3      2      0      0      2      0      3      0      4
      3      0   1002      4      0      1      1      8      3      0     10
      0      0      3    979      1      3      0      3      3      0     18
      0      0      1      0    959      0      2      1      0     10      9
      2      0      0      8      0    858      2      2      2      1     17
      3      2      2      0      4      1    933      0      3      0     10
      1      1      5      1      2      0      0    998      1      7     12
      1      1      3      7      1      3      3      3    925      3     24
      4      2      0      4      5      1      2      3      3    970     15

\end{lstlisting}

Ostatnia operacja powtórzona dla \texttt{ed} będącego zbiorem "polskich" cyfr oraz \texttt{el} będącego zbiorem odpowiadających mu etykiet dała następujący rezultat:

\begin{lstlisting}
> [errors rejections mx]=evaluateWithConfidence(net, ed, el, 0.57)
errors =  0.12019
rejections =  0.068391
mx =

   1591      0      6      0      0      6     11      3      3      1     13
    118    572     57     72    311     10      3    149      9     29    312
      1     11   1434      4      0      0     10     34     58      5     85
      0      2     11   1462      1     44      0      5     28     13     73
      2      6      3      4   1361     17     85      0      1     24    126
      1      1      0      8      1   1561     15      0     10      6     37
     12      2      1      0      0     19   1530      0     22      0     56
      0     14     82      6     46      3      1   1287     14     42    147
      7     17      4      9      2      5      3      2   1555      4     32
     10     12      0    123     44     52      0      5    208    947    240
\end{lstlisting}

\end{document}
